package com.nlp.algorithm.dynamic;

/**
 * 最长公共子序列问题
 * 最长公共子序列问题是要找到两个字符串间的最长公共子序列。
 * 假设有两个字符串sudjxidjs和xidjxidpolkj，其中djxidj就是他们
 * 的最长公共子序列。许多问题都可以看成是公共子序列的变形。
 * 例如语音识别问题就可以看成最长公共子序列问题。
 * 
 * 假设两个字符串分别为A=a1a2..am,B=b1b2..bn,则m为A的长度，
 * n为B的长度。那么他们的最长公共子序列分为两种情况。
 * 1、am=bn,这时他们的公共子序列一定为的长度F(m,n)=F(m-1,n-1)+am；
 * 2、am≠bn,这时他们的公共子序列一定为的长度F(m,n)=Max(F(m-1,n),F(m,n-1))；
 * @author ygsong.abcft
 * 
 * 求两个字符串之间的最长子序列
 *
 */
public class MaxCommonStr {
	
	//数组用来存储两个字符串的最长公共字序列
	public String[][] result;
	public MaxCommonStr(int m, int n) {
		result = new String[m][n];
	}
	
	public static void main(String[] args) {
		String strA = "123456789";
		String strB = "5678659";
		MaxCommonStr maxCommon = new MaxCommonStr(strA.length(), strB.length());
		String str = maxCommon.maxCommonStr(strA, strB);
		System.out.println(str);
	}

	/**
	 * 获取2个字符串的最大公共字序列
	 * @param strA
	 * @param strB
	 * @return
	 */
	private String maxCommonStr(String strA, String strB) {
		// 分别获取2个字符串的长度
		int lenA = strA.length();
		int lenB = strB.length();

		// 如果字符串strA 的长度为1，那么如果strB包含字符串strA，则公共子序列为strA。否则为null
		if (lenA == 1) {
			if (strB.contains(strA)) {
				result[lenA - 1][lenA - 1] = strA;
			} else {
				result[lenA - 1][lenA - 1] = "";
			}
			return result[lenA - 1][lenA - 1];
		}

		// 如果字符串strB的长度为1，那么如果strA包含字符串strB，则公共子序列为strB。否则为null
		if (lenB == 1) {
			if (strA.contains(strB)) {
				result[lenA - 1][lenA - 1] = strB;
			} else {
				result[lenA - 1][lenA - 1] = "";
			}
			return result[lenA - 1][lenA - 1];
		}
		
		//如果字符串strA的最后一位和strB的最后一位相同的话
		if (strA.charAt(lenA-1) == strB.charAt(lenB-1)) {
			//先判断数组result[lenA-2][lenB-2] == null.这样可以减少一些重复运算
			if (result[lenA-2][lenB-2] == null) {
				//求strA和strB都去除最后一位剩余字符串的最大公共子序列f
				result[lenA-2][lenB-2] = maxCommonStr(strLenSub(strA),strLenSub(strB));
			}
			//strA和strB的最大公共字序列就是他们各去除最后一位剩余字符串的最大公共子序列+strA或者strB的最后一位
			result[lenA-1][lenB-1] = result[lenA-2][lenB-2]+ strA.charAt(lenA-1);
		}else {
			//否则
			if (result[lenA - 2][lenB-1] == null) {
				//计算strA去除最后一位后和strB的最大子序列
				result[lenA-2][lenB-1] = maxCommonStr(strLenSub(strA), strB);
			}
			if (result[lenA-1][lenB-2] == null) {
				//计算strB去除最后一位后和strA的最大子序列
				result[lenA-1][lenB-2] = maxCommonStr(strA, strLenSub(strB));
			}
			result[lenA-1][lenB-1] = max(result[lenA-2][lenB-1], result[lenA-1][lenB-2]);
		}
		return result[lenA-1][lenB-1];
	}

	private String max(String strA, String strB) {
		if (strA == null && strB == null) {
			return "";
		}else if (strA == null) {
			return strB;
		}else if (strB == null) {
			return strA;
		}
		if (strA.length() > strB.length()) {
			return strA;
		}
		return strB;
	}

	/**
	 * 使字符串去除最后一位，返回该新的字符串
	 * @param str
	 * @return
	 */
	private String strLenSub(String str) {
		return str.substring(0, str.length()-1);
	}

}
